Khu vực này từng thuộc về Quận Pitten, được thừa kế bởi Phiên hầu tước Ottokar III của Steiermark vào năm 1158. Sau khi vương triều Otakar tuyệt tự sau cái chết của con trai ông Ottokar IV, Công quốc Steiermark được chuyển cho Nhà Babenberg của Áo theo Hiệp ước Georgenberg. Công tước Leopold V của Áo thành lập thị trấn vào năm 1194[3] và tài trợ việc xây dựng một pháo đài gần biên giới Hungary bằng tiền chuộc vua Anh Richard Sư tử tâm, người mà trước đó ông đã bắt và giam giữ tại Lâu đài Dürnstein. Năm 1241, một toán kị binh Mông Cổ nhỏ đã đột kích Neustadt trong cuộc xâm lược của Mông Cổ ở Đế quốc La Mã Thần thánh nhưng sau đó đã bị Công tước Friederich và các hiệp sĩ của mình đẩy lui.[4] Năm 1246, người Hungary chiến thắng người Áo.[5]

Wiener Neustadt, ít nhiều có nghĩa là New Vienna ("Thành phố Viên mới"), đã giành được những đặc quyền quan trọng được trao cho thành phố để giúp nó phát triển thịnh vượng. Nó vẫn là một phần của Styria. Sau Trận Marchfeld năm 1278, Wiener Neustadt rơi vào tay Nhà Habsburg và vào năm 1379 trở thành một công quốc cấu thành của Nội Áo. Vào thế kỷ 15, Wiener Neustadt trải qua một thời kỳ bùng nổ dân số khi Hoàng đế Friedrich III nhà Habsburg đến cư trú ở đây và thành lập Giáo phận Wiener Neustadt vào năm 1469. Vợ ông là Leonor của Bồ Đào Nha qua đời ở Wiener Neustadt vào năm 1467 và nhà thờ hậu Gothic của tu viện cổ Dòng Xitô có một tượng đài tưởng nhớ bà.[5] Wappenwand (bức tường quốc huy) tại lâu đài địa phương trưng bày các quốc huy của lãnh thổ của ông ở giữa. Con trai ông là Maximilian I đặt triều đình của mình ở Wiener Neustadt và được chôn cất tại Nhà thờ St. George ở đây. Thị trấn sau đó cũng có một cộng đồng Do Thái lớn với Giáo sĩ Israel Isserlin là thành viên đáng chú ý nhất cho đến khi toàn bộ người Do Thái bị trục xuất theo lệnh của Hoàng đế Maximilian I vào năm 1496.

Vua Mátyás Corvin của Hungary, một đối thủ lâu năm của nhà Habsburg đã chinh phục thành phố vào tháng 8 năm 1487 sau khi bao vây thành phố này trong hai năm. Theo truyền thuyết, ông đã dành tặng Cúp Corvinus tuyệt đẹp cho cư dân sau chiến thắng của mình. Maximilian I đã tìm cách tái chiếm thành phố quê hương vào năm 1490. Trong thế kỷ 16, Wiener Neustadt không còn là nơi cư trú của hoàng gia và không còn là nơi quan trọng. Tuy nhiên, nó vẫn được coi là bức tường thành chống lại người Thổ và Kuruc.

Neustadt là nơi mà hoàng đế Rudolf II đã ban cho tín đồ Tin lành Bohemia vào năm 1609, Majestätsbrief hay chứng thư về quyền bình đẳng. Việc thu hồi bằng chứng thư này đã giúp kết thúc Chiến tranh ba mươi năm.[5]

Năm 1751, thành phố nhận được sự chú ý lớn hơn khi Hoàng hậu Maria Theresia của Áo quyết định thành lập Học viện Quân sự đầu tiên trên thế giới, lấy lâu đài hoàng gia trong thành phố làm cơ sở. Học viện Quân sự Theresia hoạt động từ năm 1752 cho đến ngày nay với chỉ một vài lần bị gián đoạn (Erwin Rommel được bổ nhiệm làm chỉ huy sau Anschluss ở Áo vào năm 1938). Năm 1768, Wiener Neustadt bị phá hủy bởi một trận động đất làm hư hại lâu đài, lâu đài được xây dựng lại theo kế hoạch của kiến trúc sư Nicolò Pacassi.[6] Năm 1785, Hoàng đế Joseph II nhà Habsburg đã chuyển Toà thánh giáo phận Wiener Neustadt cho Sankt Pölten.

Vào thế kỷ 19, thành phố gần như được xây dựng lại hoàn toàn sau trận hỏa hoạn tàn phá năm 1834,[5] trở thành một thành phố công nghiệp, đặc biệt là sau khi khai trương Đường sắt Nam Áo vào năm 1841. Năm 1909, "sân bay chính thức đầu tiên của Áo" được khánh thành ở phía bắc thành phố.[7] Nó phục vụ như một sân tập cho những người tiên phong về máy bay Igo Etrich, Karl Illner và Adolf Warchalowski tiến hành các thử nghiệm.

Cuộc đình công ở Áo-Hung vào tháng 1 năm 1918 được bắt đầu ở Wiener Neustadt bởi các công nhân từ nhà máy Daimler Áo chuyên sản xuất vũ khí, lấy cảm hứng từ việc đảng Bolshevik giành chính quyền để thực hiện hành động đình công để phản đối chiến tranh. Một yếu tố quan trọng trong cuộc đình công là việc giảm một nửa khẩu phần bột mì. Porsche đã gặp các công nhân và đồng ý đến Vienna để nói chuyện với Bộ trưởng Bộ Lương thực. Tuy nhiên, lời cầu xin công nhân quay trở lại làm việc của ông đã bị phớt lờ và họ đã diễu hành ở Tòa thị chính. Tại đây họ cùng với các công nhân khác từ nhà máy đầu máy, xưởng sản xuất bộ tản nhiệt, xưởng máy bay và các nhà máy đạn dược địa phương của G. Rath và Lichtenwörther. Vào ngày 14 tháng 1, hơn 10.000 công nhân đã tập trung bên ngoài tòa thị chính để phàn nàn về việc giảm một nửa khẩu phần bột mì. Lấy cảm hứng từ Cách mạng Nga, các công nhân đã thành lập Hội đồng công nhân.

Trong Chiến tranh thế giới thứ hai, mục tiêu chiến lược ở Wiener Neustadt bao gồm các bãi tập kết, nhà máy Wiener Neustädter Flugzeugwerke (WNF),[8] và hai nhà máy Raxwerke sử dụng lao động cưỡng bức bị giam giữ tại trại tập trung Mauthausen-Gusen đã nhiều lần bị bị đánh bom. Các hoạt động ném bom như Operation Pointblank chỉ để lại 18 trong số 4.000 tòa nhà không bị hư hại.[9]